import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,2]
 * 输出:
 * [
 * [2],
 * [1],
 * [1,2,2],
 * [2,2],
 * [1,2],
 * []
 * ]
 */
class Solution {

    public static void main(String[] args) {
        //System.out.println(subsetsWithDup(new int[]{1, 1, 2, 2}));
        System.out.println(subsetsWithDup(new int[]{5, 5, 5, 5}));
    }

    public static List<List<Integer>> all;

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        // 排序
        Arrays.sort(nums);
        all = new ArrayList<List<Integer>>();
        all.add(new ArrayList<Integer>());
        for (int i = 0, pre = 0; i < nums.length; i++) {
            pre = subSets(nums, i, pre);
        }
        return all;
    }

    /**
     * 从num里面选第i个添加到结果中
     *
     * @param nums 队列
     * @param i    第i个
     * @param pre  前面还有几个是相等的
     */
    public static int subSets(int[] nums, int i, int pre) {
        int start = 0;
        int size = all.size();
        if (i > 0 && nums[i] == nums[i - 1]) {
            // 如果与上一个值一样
            pre++;
            start = size - (size / (pre + 1));
        } else {
            pre = 0;
        }
        List<Integer> newList;
        for (int j = start; j < size; j++) {
            newList = new ArrayList<Integer>(all.get(j));
            newList.add(nums[i]);
            all.add(newList);
        }
        return pre;
    }
}